package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-23 16:41
 **/
public class LeetCode187 {

    private static final int L = 10;

    //hash表法
    /*public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len - L + 1; ++i) {
            String temp = s.substring(i, i + L);
            map.put(temp, map.getOrDefault(temp, 0) + 1);
            if (map.get(temp) == 2) {
                res.add(temp);
            }
        }

        return res;
    }*/

    //滑动窗口+哈希表+位运算
    Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
        put('A', 0);
        put('C', 1);
        put('G', 2);
        put('T', 3);
    }};

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        int n = s.length();
        //字符串长度小于10的肯定不存在重复的
        if (n <= L) {
            return res;
        }
        //用一个int类型的数的低20位表示10个2位的滑动窗口
        int x = 0;

        for (int i = 0; i < L - 1; ++i) {
            //x << 2: x左移两位
            //x = x | bin[ch]: 新字符进入窗口
            x = (x << 2) | bin.get(s.charAt(i));
        }
        //使用map统计每10个字符转成int数的频次
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <= n - L; ++i) {
            //x = x & ((1 << 20) - 1): 窗口最左边的字符离开窗口,只保留低20位的内容
            x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) == 2) {
                res.add(s.substring(i, i + L));
            }
        }
        return res;
    }

}
